{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #is Array a Preorder of Some ‌Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPreorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组是否表示某二叉树的前序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个以 <strong>0</strong> 为起始索引的整数 <strong>二维数组</strong> <code>nodes</code> ，你的任务是确定给定的数组是否表示某个 <strong>二叉</strong> 树的 <strong>前序</strong> 遍历。</p>\n",
    "\n",
    "<p>对于每个索引 <code>i</code> ，<code>nodes[i] = [id, parentId]</code> ，其中 <code>id</code> 是索引 <code>i</code> 处节点的 id，<code>parentId</code> 是其在树中的父节点 id（如果该节点没有父节点，则 <code>parentId = -1</code> ）。</p>\n",
    "\n",
    "<p>如果给定的数组表示某个树的前序遍历，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><strong>注意</strong>：树的 <strong>前序</strong> 遍历是一种递归的遍历方式，它首先访问当前节点，然后对左子节点进行前序遍历，最后对右子节点进行前序遍历。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nodes = [[0,-1],[1,0],[2,0],[3,2],[4,2]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>给定的 nodes 数组可以构成下面图片中的树。 \n",
    "我们可以验证这是树的前序遍历，首先访问节点 0，然后对左子节点进行前序遍历，即 [1] ，然后对右子节点进行前序遍历，即 [2,3,4] 。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/04/1.png\" style=\"padding: 10px; background: #fff; border-radius: .5rem; width: 250px; height: 251px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nodes = [[0,-1],[1,0],[2,0],[3,1],[4,1]]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>给定的 nodes 数组可以构成下面图片中的树。 \n",
    "对于前序遍历，首先访问节点 0，然后对左子节点进行前序遍历，即 [1,3,4]，但是我们可以看到在给定的顺序中，2 位于 1 和 3 之间，因此它不是树的前序遍历。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/04/2.png\" style=\"padding: 10px; background: #fff; border-radius: .5rem; width: 250px; height: 251px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nodes.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nodes[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= nodes[i][0] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-1 &lt;= nodes[i][1] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>生成的输入保证 <code>nodes</code> 可以组成二叉树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [is-array-a-preorder-of-some-binary-tree](https://leetcode.cn/problems/is-array-a-preorder-of-some-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [is-array-a-preorder-of-some-binary-tree](https://leetcode.cn/problems/is-array-a-preorder-of-some-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,-1],[1,0],[2,0],[3,2],[4,2]]', '[[0,-1],[1,0],[2,0],[3,1],[4,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack = [-1]\n",
    "        for node, pa in nodes:\n",
    "            while stack and stack[-1] != pa:\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                return False\n",
    "\n",
    "            stack.append(node) \n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack = [-1]\n",
    "        for node,pa in nodes:\n",
    "            while stack and stack[-1]!=pa:\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                return False\n",
    "\n",
    "            stack.append(node) \n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack=[-1]\n",
    "        for i,j in nodes:\n",
    "            while stack and stack[-1]!=j:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                return False\n",
    "            stack.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        ls=[-1]\n",
    "        for s,f in nodes:\n",
    "            while ls and ls[-1]!=f:\n",
    "                ls.pop()\n",
    "            if not ls:return False\n",
    "            ls.append(s)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        st = [-1]\n",
    "        for u, p in nodes:\n",
    "            while st and st[-1] != p:\n",
    "                st.pop()\n",
    "            if not st:\n",
    "                return False\n",
    "            st.append(u)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        s = [-1]\n",
    "        for i,j in nodes:\n",
    "            while s and s[-1] != j: s.pop()\n",
    "            if not s: return False\n",
    "            s.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        # if nodes[0][1] != -1:\n",
    "        #     return False \n",
    "\n",
    "        stack = [-1]\n",
    "        for i, p in nodes:\n",
    "            while stack and stack[-1] != p:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                return False \n",
    "            stack.append(i)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack = deque([-1])\n",
    "        for i, p in nodes:\n",
    "            while stack and stack[-1] != p:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                return False \n",
    "            stack.append(i)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        if nodes[0][1] != -1:\n",
    "            return False \n",
    "\n",
    "        stack = [nodes[0][0]]\n",
    "        for i, p in nodes[1:]:\n",
    "            while stack and stack[-1] != p:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                return False \n",
    "            stack.append(i)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack=[-1]\n",
    "        for i,j in nodes:\n",
    "            while stack and stack[-1]!=j:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                return False\n",
    "            stack.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        s = [-1, ]\n",
    "        for c,p in nodes:\n",
    "            while s and s[-1] != p:\n",
    "                s.pop()\n",
    "            if not s:\n",
    "                return False\n",
    "            s.append(c)\n",
    "        return True\n",
    "            \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        s = [-1]\n",
    "        for a, b in nodes:\n",
    "            while s and s[-1] != b:\n",
    "                s.pop()\n",
    "            if not s:\n",
    "                return False \n",
    "            s.append(a)\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack = []\n",
    "        # Start with a dummy root node with id -1\n",
    "        stack.append(-1)\n",
    "        \n",
    "        for node in nodes:\n",
    "            id, parentId = node\n",
    "            # Pop nodes from the stack until we find a match for parentId\n",
    "            while stack[-1] != parentId:\n",
    "                stack.pop()\n",
    "                # If the stack is empty and we haven't found a match, return False\n",
    "                if not stack:\n",
    "                    return False\n",
    "            # Push the current node's id onto the stack\n",
    "            stack.append(id)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        # if nodes[0][1] != -1:\n",
    "        #     return False \n",
    "\n",
    "        stack = deque()\n",
    "        stack.append(-1)\n",
    "        for i, p in nodes:\n",
    "            while stack and stack[-1] != p:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                return False \n",
    "            stack.append(i)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dfs\n",
    "    # 用一个栈模拟前序遍历过程，只要每个非根节点都找得到父节点就说明序列没问题。假设-1是个真实存在的节点可以避免特判根节点。时空复杂度O(n)\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        stack = [-1]\n",
    "        for node, pa in nodes:\n",
    "            while stack and stack[-1] != pa:\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                return False\n",
    "\n",
    "            stack.append(node) \n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        m=-1\n",
    "        for i,j in nodes:\n",
    "            m=max(m,max(i,j))\n",
    "        n=len(nodes)\n",
    "        g=[[] for _ in range(m+1)]\n",
    "        start=0\n",
    "        for i,j in nodes:\n",
    "            if j>=0:\n",
    "                g[j].append(i)\n",
    "            else:\n",
    "                start=i\n",
    "        check=True\n",
    "        self.time=1\n",
    "        \n",
    "        def dfs(x,time):\n",
    "            nonlocal check\n",
    "            if len(g[x])==0:\n",
    "                return\n",
    "            for i in g[x]:\n",
    "                if nodes[self.time]!=[i,x]:\n",
    "                    check=False\n",
    "                    return \n",
    "                else :\n",
    "                    self.time+=1\n",
    "                    dfs(i,self.time)\n",
    "        dfs(start,self.time)\n",
    "        return check"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        m=-1\n",
    "        for i,j in nodes:\n",
    "            m=max(m,max(i,j))\n",
    "        n=len(nodes)\n",
    "        g=[[] for _ in range(m+1)]\n",
    "        start=0\n",
    "        for i,j in nodes:\n",
    "            if j>=0:\n",
    "                g[j].append(i)\n",
    "            else:\n",
    "                start=i\n",
    "        check=True\n",
    "        self.time=1\n",
    "        def dfs(x,time):\n",
    "            nonlocal check\n",
    "            if len(g[x])==0:\n",
    "                return\n",
    "            for i in g[x]:\n",
    "                if nodes[self.time]!=[i,x]:\n",
    "                    check=False\n",
    "                    return \n",
    "                else :\n",
    "                    self.time+=1\n",
    "                    dfs(i,self.time)\n",
    "                    if not check:\n",
    "                        return\n",
    "        dfs(start,self.time)\n",
    "        return check\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPreorder(self, nodes: List[List[int]]) -> bool:\n",
    "        m=-1\n",
    "        for i,j in nodes:\n",
    "            m=max(m,max(i,j))\n",
    "        n=len(nodes)\n",
    "        g=[[] for _ in range(m+1)]\n",
    "        start=0\n",
    "        for i,j in nodes:\n",
    "            if j>=0:\n",
    "                g[j].append(i)\n",
    "            else:\n",
    "                start=i\n",
    "        check=True\n",
    "        self.time=1\n",
    "        def dfs(x,time):\n",
    "            nonlocal check\n",
    "            if len(g[x])==0:\n",
    "                return\n",
    "            for i in g[x]:\n",
    "                if nodes[self.time]!=[i,x]:\n",
    "                    check=False\n",
    "                    return \n",
    "                else :\n",
    "                    self.time+=1\n",
    "                    dfs(i,self.time)\n",
    "        dfs(start,self.time)\n",
    "        return check\n",
    "                \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
